1. Field of the Invention
The present invention relates to an integrated circuit structure for a convolutive Viterbi decoder, and more specifically to the integrated structure for the add-compare-select units of the decoder.
2. Discussion of the Related Art
Convolutive coding and decoding are used to reduce the amount of errors in digital signal transmission. In a convolutive Viterbi decoder, one add-compare-select unit (ACS) is associated with each node of a so-called "trellis". Each node of the trellis corresponds to a possible state of a shift register used in convolutive coding.
Since the present invention relates only to the interconeect structure of ACS units, it is not necessary to recall the operation of a convolutive Viterbi decoder which is well known in the art. Only those elements necessary for the understanding of the invention are described hereafter.
FIG. 1 illustrates a generic trellis for building any N-state trellis. A state 2n and a state 2n+1 are both linked to a state n and a state n+N/2. Number n is any positive integer and numbers 2n and 2n+1 are defined modulo-N. The links between states correspond to transitions determined by symbols received by the decoder. In this example, each symbol contains two information bits. The transitions from state n to state 2n and from state n+N/2 to state 2n+1 correspond to the reception of a symbol ab, where a is equal to 1 or 0 and b is equal to 1 or 0 according to the value of 2n. The transitions from state n to state 2n+1 and from state n+N/2 to state 2n correspond to the reception of symbol ab.
FIG. 2 shows essential components of the ACS unit associated with state 2n. This unit ACS(2n) is meant to update an associated path metric PM(2n) in a register 10 and to issue a decision D(2n). Each path metric is a 7-bit number, for example.
Unit ACS(2n) includes an adder 12 which receives path metric PM(n) of the ACS unit associated with state n and a branch metric BMab associated, in the present example, with symbol ab. A second adder 13 receives the path metric PM(n+N/2) issued by the ACS unit associated with state n+N/2 and a branch metric BMab associated, in the present example, with symbol ab.
A branch metric BMx is a five-bit number, for example, which is smaller as the probability of having received the corresponding symbol x increases. Similarly, for a given ACS unit, the lower the value of a path metric PM(y), the more likely it is for the received symbol to be the one corresponding to the transition of state y to the state associated with the ACS unit.
Decision D(2n) is issued by a comparator 15 receiving the outputs of adders 12 and 13. It controls a multiplexer 17 to select, from among the outputs of adders 12 and 13, that output with the lowest value. Thus, decision D(2n) indicates the most likely preceding state among states n and n+N/2. The output of multiplexer 17 is stored in register 10 as the path metric PM(2n) to be used upon receipt of the following symbol.
The ACS unit associated with state 2n+1 is similar to that of FIG. 2, except that adder 12 receives branch metric BMab and adder 13 receives branch metric BMab.
In currently used convolutive decoders, the trellis has a relatively significant size, for example of 64 states. Thus, the interconnections between ACS units become complex and particular care is required for the positioning and routing of these ACS units on an integrated circuit so as not to occupy a large surface area and affect the operating speed.
An optimized solution for the positioning and routing of ACS units has been found by Sparso and is described in IEEE Journal of Solid State Circuits, Vol. 26, n.degree. 2, February 1991, pp. 90-97, "An Area-Efficient Topology for VLSI Implementation of Viterbi Decoders and Other Shuffle-Exchange Type Structures".
FIG. 3 illustrates the general principle of Sparso's placing and routing. The ACS units are gathered by pairs in two columns separated by a common routing channel 20. Each pair includes, juxtaposed along the width of the corresponding column, the units associated with states 2n and 2n+1 (modulo-N, n being any number). These two ACS units receive the path metric PM issued by the ACS unit associated with state n or with state n+N/2 which is located, as shown, in a previous close pair, on the side away from the common channel 20. The missing path metric arrives to the ACS units associated with states 2n and 2n+1 via common channel 20. There remains a local routing channel 22 between two pairs of ACS units.
FIG. 4 schematically illustrates an ACS network structure, obtained by using the Sparso method in the example of a 64-state trellis. The ACS units are illustrated by cells designated by the associated states.
The Sparso method is optimal when using integration technologies with two metallization layers. However, in more recent technologies, there are three metallization layers. When the Sparso method is transposed to a technology with three metallization layers, the size of the ACS network cannot be significantly reduced with respect to the same trellis implemented in a technology with two metallization layers.